package targetToOffer.sixteenthDay;

import org.omg.CORBA.INTERNAL;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Godc
 * @description
 */
public class BuildTree {
}
class BuildTreeSolution {
    int[] postArr;
    Map<Integer,Integer> map = new HashMap<>();

    /**
     * 中序加后序得到二叉树
     * @param inorder
     * @param postorder
     * @return
     */
    public TreeNode buildTree(int[] inorder, int[] postorder){
        this.postArr = postorder;
        for(int i=0;i<inorder.length;i++) {
            map.put(inorder[i], i);
        }
        return rerc(postorder.length-1,0,inorder.length-1);
    }

    /**
     * left和right都是中序遍历确定的左右边界，
     * root是根据边界关系在后序数组中的下标
     * @param root
     * @param left
     * @param right
     * @return
     */
    public TreeNode rerc(int root,int left,int right){
        if(left>right) return null;
        int rootVal = postArr[root];
        TreeNode node = new TreeNode(rootVal);
        // 确定root在中序数组中的下标
        int i = map.get(root);
        node.left = rerc(root-right+i-1,left,i-1);
        node.right = rerc(root-1,i+1,right);
        return node;
    }
}

/**
 * 前序+中序
 */
class Solution {
    int[] preArr;
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        preArr = preorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return rerc(0,0,inorder.length-1);
    }
    public TreeNode rerc(int root,int left,int right){
        if(left>right) return null;
        int val = preArr[root];
        int i = map.get(val);
        TreeNode node = new TreeNode(val);
        node.left = rerc(root+1,left,i-1);
        node.right = rerc(root+i-left+1,i+1,right);
        return node;
    }

}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
